
// 二叉搜索树（BST）节点模板类
// K 表示键（key）类型，V 表示值（value）类型
template<class K, class V>
struct BSTNode {
    K _key;                 // 节点存储的键
    V _value;               // 节点存储的值
    BSTNode<K, V>* _left;   // 左子节点指针
    BSTNode<K, V>* _right;  // 右子节点指针

    // 构造函数
    BSTNode(const K& key, const V& value)
        : _key(key)
        , _value(value)
        , _left(nullptr)
        , _right(nullptr)
    {}
};

// 二叉搜索树（BST）模板类
template<class K, class V>
class BSTree {
    typedef BSTNode<K, V> Node;  // 节点类型别名定义
public:
    // 默认构造函数
    BSTree() = default;

    // 拷贝构造函数（深拷贝）
    BSTree(const BSTree<K, V>& t) {
        _root = Copy(t._root);
    }

    // 赋值运算符重载（使用拷贝交换技术）
    BSTree<K, V>& operator=(BSTree<K, V> t) {
        swap(_root, t._root);
        return *this;
    }

    // 析构函数
    ~BSTree() {
        Destroy(_root);
        _root = nullptr;
    }

    // 插入键值对
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;

        // 查找合适的插入位置
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;  // 键已存在，插入失败
            }
        }

        // 创建新节点
        cur = new Node(key, value);

        // 将新节点连接到父节点
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }
        return true;
    }

    // 查找键对应的节点
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                cur = cur->_left;
            }
            else {
                return cur;  // 找到键对应的节点
            }
        }
        return nullptr;  // 未找到
    }

    // 删除键对应的节点
    bool Erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;

        // 查找要删除的节点
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                // 找到要删除的节点，分三种情况处理

                // 情况1：要删除的节点只有右子树或没有子树
                if (cur->_left == nullptr) {
                    if (parent == nullptr) {  // 删除的是根节点
                        _root = cur->_right;
                    }
                    else {
                        if (parent->_left == cur) {
                            parent->_left = cur->_right;
                        }
                        else {
                            parent->_right = cur->_right;
                        }
                    }
                    delete cur;
                    return true;
                }
                // 情况2：要删除的节点只有左子树
                else if (cur->_right == nullptr) {
                    if (parent == nullptr) {  // 删除的是根节点
                        _root = cur->_left;
                    }
                    else {
                        if (parent->_left == cur) {
                            parent->_left = cur->_left;
                        }
                        else {
                            parent->_right = cur->_left;
                        }
                    }
                    delete cur;
                    return true;
                }
                // 情况3：要删除的节点有左右子树
                else {
                    // 找到右子树中最小的节点（替代节点）
                    Node* rightMinP = cur;
                    Node* rightMin = cur->_right;
                    while (rightMin->_left) {
                        rightMinP = rightMin;
                        rightMin = rightMin->_left;
                    }

                    // 用替代节点的值替换当前节点的值
                    cur->_key = rightMin->_key;
                    cur->_value = rightMin->_value;

                    // 删除替代节点
                    if (rightMinP->_left == rightMin) {
                        rightMinP->_left = rightMin->_right;
                    }
                    else {
                        rightMinP->_right = rightMin->_right;
                    }
                    delete rightMin;
                    return true;
                }
            }
        }
        return false;  // 未找到要删除的键
    }

    // 中序遍历（按键升序输出）
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

private:
    // 递归中序遍历辅助函数
    void _InOrder(Node* root) {
        if (root == nullptr) {
            return;
        }
        _InOrder(root->_left);
        cout << root->_key << ":" << root->_value << endl;
        _InOrder(root->_right);
    }

    // 递归销毁树辅助函数
    void Destroy(Node* root) {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

    // 递归拷贝树辅助函数
    Node* Copy(Node* root) {
        if (root == nullptr) return nullptr;
        Node* newRoot = new Node(root->_key, root->_value);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

private:
    Node* _root = nullptr;  // 树的根节点
};

// 主函数1：字典应用示例
int main() {
    BSTree<string, string> dict;
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("insert", "插入");
    dict.Insert("string", "字符串");

    string str;
    while (cin >> str) {
        auto ret = dict.Find(str);
        if (ret) {
            cout << "->" << ret->_value << endl;
        }
        else {
            cout << "无此单词，请重新输入" << endl;
        }
    }
    return 0;
}

// 主函数2：统计水果出现次数示例
int main() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
                    "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

    BSTree<string, int> countTree;

    for (const auto& str : arr) {
        auto ret = countTree.Find(str);
        if (ret == NULL) {
            countTree.Insert(str, 1);  // 第一次出现的水果
        }
        else {
            ret->_value++;  // 已存在的水果，计数增加
        }
    }

    countTree.InOrder();  // 输出统计结果
    return 0;
}